// 二叉树
class BinaryTree {
    /**
     *
     * @param root{HeroNode}
     */
    setRoot (root) {
        this.root = root
    }

    /**
     * 前序遍历
     */
    preOrder () {
        if (this.root !== null) {
            this.root.preOrder()
        } else {
            console.log('二叉树为空')
        }
    }

    /**
     * 中序遍历
     */
    infixOrder () {
        if (this.root !== null) {
            this.root.infixOrder()
        } else {
            console.log('二叉树为空')
        }
    }

    /**
     * 后序遍历
     */
    postOrder () {
        if (this.root !== null) {
            this.root.postOrder()
        } else {
            console.log('二叉树为空')
        }
    }

    /**
     * 前序查找
     * @param no
     * @returns {null|HeroNode}
     */
    preOrderSearch (no) {
        if (this.root !== null) {
            return this.root.preOrderSearch(no)
        } else {
            return null
        }
    }

    /**
     * 中序查找
     * @param no
     * @returns {null|HeroNode}
     */
    infixOrderSearch (no) {
        if (this.root !== null) {
            return this.root.infixOrderSearch(no)
        } else {
            return null
        }
    }

    /**
     * 后序查找
     * @param no
     * @returns {null|HeroNode}
     */
    postOrderSearch (no) {
        if (this.root !== null) {
            return this.root.postOrderSearch(no)
        } else {
            return null
        }
    }

    /**
     * 删除节点
     * @param no
     */
    delete(no){
        if (this.root !== null) {
            if(this.root.no===no){
                this.root=null
            }else{
                this.root.delete(no)
            }
        } else {
            return null
        }
    }
}

class HeroNode {
    no = ''
    name = ''
    left = null
    right = null

    /**
     *
     * @param no {number}
     * @param name {string}
     */
    constructor (no, name) {
        this.no = no
        this.name = name
    }

    toString () {
        return `HeroNode [no=${this.no},name=${this.name}]`
    }

    /**
     * 前序遍历
     * 1.先输出当前节点（初始的时候是root节点）
     * 2.如果左子节点不为空，则递归继续前序遍历
     * 3.如果右子节点不为空，则递归继续前序遍历
     */
    preOrder () {
        // 1.先输出当前节点（初始的时候是root节点）
        console.log(this.toString())
        // 2.如果左子节点不为空，则递归继续前序遍历
        if (this.left !== null) {
            this.left.preOrder()
        }
        // 3.如果右子节点不为空，则递归继续前序遍历
        if (this.right !== null) {
            this.right.preOrder()
        }
    }

    /**
     * 中序遍历
     * 1.如果左子节点不为空，则递归中序遍历
     * 2.输出当前节点
     * 3.如果右子节点不为空，则递归中序遍历
     */
    infixOrder () {
        // 1.如果左子节点不为空，则递归中序遍历
        if (this.left !== null) {
            this.left.infixOrder()
        }
        // 2.输出当前节点
        console.log(this.toString())
        // 3.如果右子节点不为空，则递归中序遍历
        if (this.right !== null) {
            this.right.infixOrder()
        }
    }

    /**
     * 后序遍历
     * 1.如果左子节点不为空，则递归后序遍历
     * 2.如果右子节点不为空，则递归后序遍历
     * 3.输出当前节点
     */
    postOrder () {
        // 1.如果左子节点不为空，则递归后序遍历
        if (this.left !== null) {
            this.left.postOrder()
        }
        // 2.如果右子节点不为空，则递归后序遍历
        if (this.right !== null) {
            this.right.postOrder()
        }
        // 3.输出当前节点
        console.log(this.toString())
    }

    /**
     * 前序查找
     * @param no
     */
    preOrderSearch (no) {
        console.log('进入前序查找')
        // 比较当前节点
        if (this.no === no) {
            return this
        }
        // 判断左子节点 如果不为空 则递归前序查找
        // 如果左递归查找到了节点 则返回
        let resNode = null
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no)
        }
        if (resNode !== null) {
            return resNode
        }
        // 判断右子节点 如果不为空 则递归前序查找
        // 如果右递归查找到了节点 则返回
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no)
        }
        return resNode
    }

    /**
     * 中序查找
     * @param no
     */
    infixOrderSearch (no) {
        // 判断左子节点 如果不为空 则递归中序查找
        // 如果左递归查找到了节点 则返回
        let resNode = null
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no)
        }
        if (resNode !== null) {
            return resNode
        }
        console.log('进入中序查找')
        // 如果没有找到 比较当前节点
        if (this.no === no) {
            return this
        }
        // 判断右子节点 如果不为空 则递归中序查找
        // 如果右递归查找到了节点 则返回
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no)
        }
        return resNode
    }

    /**
     * 后序查找
     * @param no
     */
    postOrderSearch (no) {
        // 判断左子节点 如果不为空 则递归后序查找
        // 如果左递归查找到了节点 则返回
        let resNode = null
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no)
        }
        if (resNode !== null) {
            return resNode
        }
        // 判断右子节点 如果不为空 则递归后序查找
        // 如果右递归查找到了节点 则返回
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no)
        }
        if (resNode !== null) {
            return resNode
        }
        console.log('进入后序查找')
        // 如果没有找到 比较当前节点
        if (this.no === no) {
            return this
        }
        return resNode
    }

    /**
     * 删除节点
     * @param no
     */
    delete (no) {
        if (this.left !== null && this.left.no === no) {
            this.left = null
            return
        }

        if (this.right !== null && this.right.no === no) {
            this.right = null
            return
        }

        if (this.left !== null) {
            this.left.delete(no)
        }

        if (this.right !== null) {
            this.right.delete(no)
        }
    }
}

function main () {
    let binaryTree = new BinaryTree()
    let node1 = new HeroNode(1, '1')
    let node2 = new HeroNode(2, '2')
    let node3 = new HeroNode(3, '3')
    let node4 = new HeroNode(4, '4')
    let node5 = new HeroNode(5, '5')

    node1.left = node2
    node1.right = node3
    node3.left = node4
    node3.right = node5
    //    1
    // 2      3
    //      4    5

    binaryTree.setRoot(node1)
    console.log('前序遍历') // 12345
    binaryTree.preOrder()
    console.log('中序遍历') // 21435
    binaryTree.infixOrder()
    console.log('后序遍历') // 24531
    binaryTree.postOrder()

    console.log('前序查找') // 4 次
    console.log(binaryTree.preOrderSearch(4)?.toString())
    console.log('中序查找') // 3 次
    console.log(binaryTree.infixOrderSearch(4)?.toString())
    console.log('后序查找') // 2 次
    console.log(binaryTree.postOrderSearch(4)?.toString())

    console.log('删除前')
    binaryTree.preOrder()
    console.log('删除后')
    binaryTree.delete(3)
    binaryTree.preOrder()
}

main()
